COMMENT ⊗   VALID 00001 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 ENDMK
C⊗;
∂15-Jan-79  0548	PEAGRE at MIT-MC (Philip E. Agre)  
Date: 15 JAN 1979 0849-EST
From: PEAGRE at MIT-MC (Philip E. Agre)
To: JRA at SU-AI, CARL at MIT-AI

Re: August '79 BYTE (LISP)
       I am in the process of preparing an article on the implementation
of functions in LISP, half philosophy-of-LISP, half assembly-language
coding hacks, which comes in 20- and 50- double-spaced-page versions.
It will appear this month (w/ luck) as a Univ. of Maryland Technical
Report under the title "Functions as Data Objects -- The Implementation
of Functions in LISP".  Would you be interested in receiving a copy
of this report with an eye towards publishing it or a version of it
(e.g., the philosophy half or the hacking half) in the August '79
LISP issue of BYTE?  
      I can be reached within 2 days as PEAGRE@MIT-MC.  I am an
undergraduate at the University of Maryland, hoping on doing AI
at MIT-AI starting in September.  I would appreciate any consideration
you might give my material.        
      - Phil Agre

∂18-Jan-79  1732	PEAGRE at MIT-MC (Philip E. Agre) 	Byte Article (trials & tribs.)
Date: 18 JAN 1979 2032-EST
From: PEAGRE at MIT-MC (Philip E. Agre)
Subject: Byte Article (trials & tribs.)
To: jra at SU-AI

John-
     I am thoroughly delighted by your interest in my paper
("Functions as Data Objects -- The Implementation of Functions
in LISP").  Right now it is being proofed by my expert staff
(Chuck Rieger, Hanan Samet, and co.) and should be ready
for TR printing by Wednesday.  (Given our
publishing services here, this could mean one week or one month
until a really neat printing returns.)  Anything on the high
side of that scale will cause me to slap a few custom copies
together within your required time parameters.  As regards
a version of the paper suitable for publishing in BYTE,
I am just now paring the Tech Report down to a paper version.
Are you most interested in the philosophy-of-LISP parts, the
assembly-language-implementation parts, or the real-live basics.
Also, what prerequisites should I assume?  I assume a LISP
tutorial will be the first-or-second article, so that I will
be able to editorialize and be understood.  You say you will
be on SU-AI Saturday&Sunday; I would like to link to
you then to ask your responses to these and other questions
regarding the issue (such mundane things as "how long should
the article be", "how many articles will there be", "what
is the status of the project--is it definate that this thing
will occur?", etc.).
     By the way, I have a list of typos from "Anatomy of LISP".
Would you like me to pass them along?  (I am a great fan of
the book.)
     Again, thanks for your interest and I will try to LINK
(w/ proper warning) to you this weekend.
     Phil Agre (PEAGRE at MIT-MC)

∂21-Jan-79  1022	PEAGRE at MIT-MC (Philip E. Agre)  
Date: 21 JAN 1979 1324-EST
From: PEAGRE at MIT-MC (Philip E. Agre)
To: jra at SU-AI

   John-
A good address for sending me the "BYTE style manual" would be:
     Phil Agre
     Department of Computer Science
     University of Maryland
     College Park, Maryland  20742
Thanks.      - Phil

∂21-Jan-79  1212	PEAGRE at MIT-MC (Philip E. Agre) 	Abstract of ''Functions as...'' (150 lines)  
Date: 21 JAN 1979 1514-EST
From: PEAGRE at MIT-MC (Philip E. Agre)
Subject: Abstract of "Functions as..." (150 lines)
To: jra at SU-AI

   John-
Following (if I understand :MAIL) is an abstract for my "Functions as
Data Objects..." paper and for all its various chapters.  These
abstracts are for a not-totally-debugged version of the paper,
which has not been fully proofed.  Also, this is the Tech. Report,
not the article.  I would hope to put the whole thing in as an
article -- it runs 40 pages with 88 lines per page, 65 columns,
double spaced, including 13 figures and 5 pages of appendix,
as well as about 4 pages worth of inter-chapter paging-up.
I would appreciate any comments you might have (anything
from "I got it" to "Here is my opinion on all these subjects...").
In any event, I am working like mad to get a real-live copy
of the report out to you.  Well, here it is...

Functions as Data Objects -- The Implementation of Functions in LISP
Philip Agre       University of Maryland at College Park     Jan '79
Global and Chapter Abstracts
January 21, 1979

Global Abstract: This paper discusses the manner in which functions are
defined and manipulated in various dialects of the LISP language.  It
is argued that the syntax and mechanisms which are usually provided
for doing such things as passing functions as arguments and returning
them as values are unnecessarily inconsistent and clumsy.  An alternative
scheme for implementing functions in LISP is presented.  It is based
on the concept of a "linker node", a construct used in Wisconsin/
Maryland LISP, and allows great uniformity in the handling of different
types of functions.  The advantages of being able to handle functions
in all the same ways as the other common data structures are demonstrated,
and one possible functions syntax is outlined and coded.

Chapter 1 - Introduction

(Abstract) It is a necessary and useful thing to treat "function" as
denoting an abstract data type with a well-defined set of construction
and selection functions.  This is especially nice in LISP, where
a major point is made of equating programs and data.  To treat this
topic further, we should make clear the distinction between external
and internal reprsentations of functions.  For example, we might say
that the external representation is a representation of the abstractly
defined algorithm being implemented and the internal representation
(functional object) is a representation of the abstractly defined
function.

Chapter 2 - Traditional Implementations of LISP Functions

It is argued that most existing LISP implementations do not make
the necessary distinction between internal and external representations
and that this makes their "funarg" facilities clumsy to use.
The discussion concentrates on MacLISP.

Chapter 3 - A Notion of "Function as Data Object"

The "linker node" makes its debut.  It is a two-word data object
whose first word is a subroutine-call instruction pointing at
an "expansion routine", one for each function type, e.g., expr,
fexpr.  The second word points at various pieces of information
which the expansion routine will use, such as a LAMBDA-expression
or a FUNCTION environment.  Linker nodes are created by "typing
functions", some of which (like LAMBDA) take s-expressions as
arguments and some of which (like FUNCTION) take other functions
as arguments.

Chapter 4 - A Possible Manifestation of the Scheme

A set of typing functions - LAMBDA, EXPR, FEXPR, MACRO, FUNCTION,
and LABEL - is defined in terms of what linker nodes they create
and how their expansion routines work.  The various implementation
assumptions are presented and we get down to some assembly-language--
level coding.  We finish by coding the EVAL function - 12 lines!

Chapter 5 - Some Examples and Consequences

A large, hairy-looking example is presented and de-mystified,
showing how many of the constructs work.  Random mumblings about
efficiency.

Chapter 6 - Addition of Function Types

To show how easy it is to add new function types in this scheme (i.e.,
because of its modularity), the CLOSURE and TRACE types are defined
and coded.

Chapter 7 - Computing with Functions

It is argued that the ability to conveniently and uniformly pass
functions around can allow the programmer flexibility in program
design.  The example which is pursued is that of computing with 
functions.  Familiar examples like COMPOSE and APL-like VECTORIZE
are seen to be easily definable.  Others are efind, and examples are
presented.

Chapter 8 - What is Meant by "Referring to a Function"?

The various vexing problems of function naming and reference are
described.  The LABEL construct is shown to be an elegant but
insufficient patch.  A more general solution is described.
It is based on the idea of a "program module", is implemented
using cirular closures, and generalizes LABEL.  However,
it too is shown not to be up to the task because of its dependence
on the deep binding mechanism.

Chapter 9 - How to Build an Association List

A really neat scheme for implementing the LISP deep-binding style
association list is presented, in which the alist is a list
of variable-list - value-list pairs.  It is shown to provide
considerable space-savings and to generalize the "list of dotted
pairs" organization without much decrease in search speed.  It
is this scheme which is assumed (by forward reference) by the
rest of the paper.

Chapter 10 - Conclusion

Summarization of major points.

Chapter 11 - Bibliography

Fairly sparse.

Chapter 12 - Appendix - A LISP Rendering of the Scheme

The set of typing functions described in the paper is implemented
in Maryland LISP.  Some fairly elegant parallels between assembly
language and LISP are hidden within.

Fin